#include <bits/stdc++.h>

using namespace std;

class Solution {
    public:
        long long minTime(vector<int>& skill, vector<int>& mana) {
            int n = skill.size(), m = mana.size();
            vector<vector<long long>> dp(n,vector<long long>(m+1, INT_MAX));
            dp[0][0] = 0;
            // 第一行无约束，直接传播结果
            for(int j = 1; j <= m; ++j){
                dp[0][j] = skill[j] * (long long)mana[0] + dp[0][j-1];
            }
            for(int i = 1; i < n; ++i){
                dp[i][m-1] = dp[i-1][m];
                for(int j = m-2; j >= 0; --j){ // 从后向前传播约束
                    dp[i][j] = max(
                        dp[i][j+1] - skill[j+1] * (long long)mana[i],
                        dp[i-1][j+1]
                    );
                }
                for(int j = 1; j <= m; ++j){ // 从前向后传播结果
                    dp[i][j] = skill[j] * (long long)mana[0] + dp[i][j-1];
                }
            }
            return dp[n-1][m];
        }
    };

int main() {
    
    //system("pause");
    return 0;
}
